This invention concerns an automated method to generate the Cyclic Redundancy Check, or CRC, particularly for the transmission of multi-protocol packets in packet-switching networks, and to minimize CRC computing time for packets including a stack of protocols, this method always being simple, reliable and efficient.
This invention also concerns the necessary tools to implement the method and all the equipments working in accordance to the method. This method can be implemented on network nodes via dedicated processing machines.
It is well known that the telecommunications industry is currently dominated by the internet, whose protocol (IP) requires messages to be suitably processed and transmitted via a stack of different protocols structured into a certain number of independent levels for data transmission.
The message to be transmitted is inserted in a packet or datagram composed of three different portions: 1) the payload, containing the message itself; 2) the header and 3) the trailer. The header and/or the trailer contain some service information, such as the type of data/packet and the IP address of the sender and receiver, and the so-called Frame Check Sequence (FCS) in order to check for proper transmission or to safeguard some specific fields of the packet.
Owing to the required number of protocols, a packet may constitute the payload for a lower level packet in the Open System Interconnect (OSI) stack, making up the cited protocol stack.
As already mentioned, transmission error detection techniques are provided in order to allow the receiver of a message, transmitted via a noisy channel (which introduces errors), to assess whether the message received has been corrupted during transmission. For these purposes, the transmitter calculates a value, called FCS, that is a function of the message and attaches it to the message being sent. The FCSs generally belong to two distinct classes characterized by different properties and computing methods respectively called checksum and Cyclic Redundancy Check (CRC) algorithms. The FCSs calculated via CRC algorithms leave the data to be transmitted intact and add a particular control word, called CRC, at the end. Therefore, for calculating the CRC, the part of the packet whose proper transmission must be checked is sent to a CRC computer that will generate the result as soon as it receives the final data. This activity is usually carried out in serial mode, so that the flow of bits enters the linear feedback shift register (LFSR) and, after the last bit has entered, an outgoing flow with the resulting CRC will be produced. In particular, the CRC depends on the characteristic generator polynomial of the LFSR.
Given a sequence of k (≧1) input bits or scalars u[t0], u[t0+1], u[t0+2], . . . , u[t0+k], representing the binary data for the LFSR input, and an n degree generator polynomial, the CRC calculation on the input data depends on the initial state x[t0] of the LFSR and on the input sequence:CRC=f(x[t0], u[t0], u[t0+1], . . . , u[t0+k])
In fact, supposing x[t0] is known, given a positive integer w less than or equal to k, we obtain:
                    x        _            ⁡              [                              t            0                    +          1                ]              =                  A        ·                              x            _                    ⁡                      [                          t              0                        ]                              +                        b          _                ·                  u          ⁡                      [                          t              0                        ]                                                  x        _            ⁡              [                              t            0                    +          2                ]              =                  A        ·                              x            _                    ⁡                      [                                          t                0                            +              1                        ]                              +                        b          _                ·                  u          ⁡                      [                                          t                0                            +              1                        ]                                ⋮                    x        _            ⁡              [                              t            0                    +          w                ]              =                  A        ·                              x            _                    ⁡                      [                                          t                0                            +              w              -              1                        ]                              +                        b          _                ·                  u          ⁡                      [                                          t                0                            +              w              -              1                        ]                              where:    x[ti] is the state vector (n,1) of the linear system described by the above equations referred to instant ti;    A is the state matrix (n,n) of the system, whose elements depend on the coefficients of the generator polynomial;    b is a vector (n,1) of the type b=[1 0 0 . . . 0]T.Substituting the (i−1)th equation in the i-th equation iteratively, we obtain the following compact form:x[t0+1]=A·x[t0]+b·u[t0]
                                          x            _                    ⁡                      [                                          t                0                            +              2                        ]                          =                              A            ·                                          x                _                            ⁡                              [                                                      t                    0                                    +                  1                                ]                                              +                                    b              _                        ·                          u              ⁡                              [                                                      t                    0                                    +                  1                                ]                                                                                                      ⁢                  =                                    A              ·                              (                                                      A                    ·                                                                  x                        _                                            ⁡                                              [                                                  t                          0                                                ]                                                                              +                                                            b                      _                                        ·                                          u                      ⁡                                              [                                                  t                          0                                                ]                                                                                            )                                      +                                          b                _                            ·                              u                ⁡                                  [                                                            t                      0                                        +                    1                                    ]                                                                                                                      ⁢                  =                                                    A                2                            ·                                                x                  _                                ⁡                                  [                                      t                    0                                    ]                                                      +                                          A                1                            ·                              b                _                            ·                              u                ⁡                                  [                                      t                    0                                    ]                                                      +                                          b                _                            ·                              u                ⁡                                  [                                                            t                      0                                        +                    1                                    ]                                                                                    ⋮                                                x            _                    ⁡                      [                                          t                0                            +              w                        ]                          =                              A            ·                                          x                _                            ⁡                              [                                                      t                    0                                    +                  w                  -                  1                                ]                                              +                                    b              _                        ·                          u              ⁡                              [                                                      t                    0                                    +                  w                  -                  1                                ]                                                                                                      ⁢                  =                                                    A                w                            ·                                                x                  _                                ⁡                                  [                                      t                    0                                    ]                                                      +                                          A                                  w                  -                  1                                            ·                              b                _                            ·                              u                ⁡                                  [                                      t                    0                                    ]                                                      +                                          A                                  w                  -                  2                                            ·                              b                _                            ·                              u                ⁡                                  [                                                            t                      0                                        +                    1                                    ]                                                      +            …            +                                                                            ⁢                              A            0                    ·                      b            _                    ·                      u            ⁡                          [                                                t                  0                                +                w                -                1                            ]                                          where A0=I is the identity matrix and Ai is the i-th power of A.
This compact form underlies a “parallel” computation method of CRC that is very useful in several applications. The following description is made on the assumption that the CRC computation is being carried out w bit at a time, so that the CRC calculation on the whole input sequence of k samples will be carried out in k/w steps, where k is a multiple of w. This simplifying hypothesis is not determining for illustrating the procedure and will in any case be removed later on.
As regards the computation method, in real applications, the input sequence may be processed in several steps, each of them operating on a subsequence of the overall sequence, as shown below.
Now, defining a binary vector uw[t] collecting the values of u from instant t to instant t+w−1 of the generic subsequence of length w (t coincides with t0 only for the first subsequence)
                    u        _            w        ⁡          [      t      ]        =      [                                        u            ⁡                          [              t              ]                                                                        u            ⁡                          [                              t                +                1                            ]                                                            ⋮                                                  u            ⁡                          [                              t                +                w                -                1                            ]                                            ]  the expression of the state vector becomesx[t+w]=Aw·x[t]+Bw·uw[t]where Bw is a matrix of dimensions (n,w) defined asBw=[Aw−1·bAw−2·b . . . A0·b]where each column of Bw is the first column of the matrices Ai (for i=0 . . . w−1). Thus, by representing in the compact form each subsequence of length w, we obtain the following representation
                    x        _            ⁡              [                              t            0                    +                      1            ·            w                          ]              =                            A          w                ·                              x            _                    ⁡                      [                          t              0                        ]                              +                        B          w                ·                                            u              _                        w                    ⁡                      [                          t              0                        ]                                                  x        _            ⁡              [                              t            0                    +                      2            ·            w                          ]              =                            A          w                ·                              x            _                    ⁡                      [                                          t                0                            +              w                        ]                              +                        B          w                ·                                            u              _                        w                    ⁡                      [                                          t                0                            +              w                        ]                                ⋮                    x        _            ⁡              [                              t            0                    +                                    (                              i                +                1                            )                        ·            w                          ]              =                            A          w                ·                              x            _                    ⁡                      [                                          t                0                            +                              i                ·                w                                      ]                              +                        B          w                ·                                            u              _                        w                    ⁡                      [                                          t                0                            +                              i                ·                w                                      ]                                ⋮                    x        _            ⁡              [                              t            0                    +                                    (                              k                /                w                            )                        ·            w                          ]              =                            A          w                ·                              x            _                    ⁡                      [                                          t                0                            +                                                (                                                            (                                              k                        /                        w                                            )                                        -                    1                                    )                                ·                w                                      ]                              +                          ⁢                          ⁢                        B          w                ·                                            u              _                        w                    ⁡                      [                                          t                0                            +                                                (                                                            (                                              k                        /                        w                                            )                                        -                    1                                    )                                ·                w                                      ]                              
The last equation represents the state vector after k/w steps (as a function of the previous step) defined as the CRC of the input sequence according to the associated generator polynomial.
The value of CRC may be rewritten as a function only of the initial state and of the input sequence by iterative substitution of state i by its expression as a function of state i−1. By carrying out the described substitution and putting p=k/w and t0=0, without losing the generality, we obtain
                                          x            _                    ⁡                      [                          p              ·              w                        ]                          =                                            A                              p                ·                w                                      ·                                          x                _                            ⁡                              [                0                ]                                              +                                    ∑                              i                =                0                                                    ⁢                                                            A                                                            (                                              p                        -                        1                        -                        i                                            )                                        ⁢                    w                                                  ·                                  B                  w                                ·                                                                                                    u                        _                                            w                                        ⁡                                          [                                              i                        ·                        w                                            ]                                                        .                                                                          ⁢                                                              ⁢                              indicates text missing or illegible when filed                                                                        [        0        ]            
Thus, the CRC may be obtained by iterating k/w=p times the following matrix form:x[t0+(i+1)·w]=Aw·x[t0+i·w]+Bw·uw[t0+i·w]  [1]CRC=x[t0+(k/w)·w]=x[p·w]  [2]where:                x is the LFSR state vector, of dimension (n,1), already introduced;        Aw is the already defined matrix (n, n);        Bw is the already defined matrix (n, w).        
The value of the elements of matrices Aw and Bw depends on the generator polynomial.
The calculation may thus be performed in k/w clock cycles with a period w times greater than the one of the serial computer that is able to process the same amount of data at the same time.
If k is not a multiple of w, then we proceed—as in the case already described—by first iterating matrix form [1] m times to obtain state x[t0+m·w], and then reusing it as the initial state in the following formula that is similar to [1] but which operates on k−m·w bit parallel datax[t0+k]=Ak−m·w·x[t0+m·w]+Bk−m·w·uk−m·w[t0+m·w].  [1A]where m is the integer quotient of k/w, and k−m·w is the remainder of the division of k by w.
In the case of a protocol stack, the CRC is calculated for each nested protocol, with the result that the CRC of lower level protocols, which include higher level protocols, depends on the CRCs of the nested protocols.
Since the CRCs (or checksums) of the internal protocols may be part of the sequence of data processed by the protocol containing them, the CRC calculation of the external protocol must be suspended until the aforesaid values become available. Usually, first one calculates the higher level CRC, then the one immediately below and so on up to the most external one.
These solutions call for a considerable amount of time because a complete processing is necessary for each level of the stack, and this means long waiting time in order to complete the CRC calculation of the higher level protocols before going on to calculate the CRC of the lower level protocol. In particular, the total time required by the CRC calculation is roughly proportional to the number of levels of the protocol stack.
Hence, in many cases, the lowest level protocol CRC calculation requires a significantly longer time than the actual duration of the packet.
As an example, see FIG. 1, which shows a stack of two protocols. Supposing that CRC (or checksum) C2 of the internal protocol is calculated on the data contained in header H2, in payload P2 and in trailer T2 of the protocol itself; CRC C1 of the external protocol covers H1, P1 and T1, where payload P1 is composed of all the higher protocol data. Note that payload P1 contains C2, that is the FCS of another protocol; moreover, C2 must be calculated on a significant part (P2+T2) of the data following it and thus, in order to complete the calculation, in any case it will be necessary to wait until all the packet (P2+T2) is available.
The network processors available on the market calculate C1 and C2 as shown in FIG. 2, which illustrates the state of activity of the computing machines in the time domain to obtain the CRC C1 as a final result. The purpose of FIG. 2 is to highlight the total calculation time in the aforesaid “traditional” mode.
The machine that calculates C2 starts operating at H2 and finishes at the end of T2; at this point, the value of C2 is available.
The machine that calculates C1 starts processing at H1 but must stop before C2 and can only resume when this field is available, because the result of the calculation of a CRC on a certain data sequence, unlike checksums, depends on the order in which data arrive.
In FIG. 2, the CRC C1 and CRC C2 are expressed according to the definition of function f introduced previously: CRC=f(x[t0], u[t0], u[t0+1], . . . , u[t0+k]). In FIG. 2, the arguments of f for calculating C2 are in the following order: the initial state X02 of the computing machine, the packet header H2, the packet payload P2 and the packet trailer T2. The same formula applies for calculating C1.
As FIG. 2 shows, the time that goes by before the external CRC C1 is available is the sum of the duration of the whole frame (H1+C1+P1+T1) and of the duration of the internal packet data following the internal CRC (or checksum) C2 (P2+T2).